Generally, database queries fall into two categories. The first category is relatively easy searches such as finding a name or number in a telephone directory. The second category is the relatively difficult problem of finding a “best” solution from a number of possibilities. The classic example of this latter category is the traveling salesman problem, e.g., finding the best path through a sales area that maximizes the number of cities visited while minimizing the distance traveled. The “brute force” solution is to identify all possible routes and then to compare each one to all the others. Unfortunately, the complexity and time required to solve the problem increases exponentially as the number of possible destinations increases.
In the airline industry, determining a set of viable itineraries to present to a passenger is a relatively difficult problem. Typically, the passenger or travel agent performing a query expects to receive an answer quickly. To perform the query, flight databases are checked for flight times and destinations to determine an itinerary. Generally, flight plans with the fewest number of stops and the lowest cost are preferred. If layovers are required, shorter layovers are typically preferred over longer layovers.
Accordingly, it is desirable to provide an efficient system and method for performing user queries of a database that is capable of overcoming the disadvantages described herein at least to some extent.